package com.hackerank.warmup;
/**
 * Counting Valleys 数山谷
 *https://www.hackerrank.com/challenges/counting-valleys/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup
 * 题目大意：
 * 1、输入一个数n，接下来输入n个字符字符串，字符为 U 或 D，U代表人向上走一步，D代表人向下走一步
 * 2、一个人从水平面按照字符串的指令走，最后回到水平面，水平面以上称为山峰，水平面以下称为山谷
 * 3、例如，一个人行走指令为 UUDDDDUU，则前4个字符，人经过一个山峰，后四个字符人经过一个山谷
 * 4、一个人从水平面到水平面以下，再回到水平面定义为一个山谷
 * 5、输出一共经过多少山谷 m
 *
 * 解题思路：
 * 1、定义计数器 = 0，遍历字符，当遇到U则将计数器+1，并判断当前的计数值是否为0，为0，表示刚经历一个山谷，则山谷数+1
 * 2、如果字符为D，则计数器-1，不做任何操作
 * 时间复杂度O(n)，空间复杂度O(1)
 * **/
public class CountingValleys {
    static int countingValleys(int n, String s) {
        int valleys = 0,length=s.length(),ele=0;
        for(int i=0;i<length;i++){
            char c = s.charAt(i);
            if(c == 'U'){
                ele ++;
                if(ele == 0)
                    valleys ++;
            }else if(c == 'D'){
                ele --;
            }
        }
        return valleys;
    }
}
